package divide.easy;

/**
 * 1. 问题描述
 *      给定一个整数数组，找出总和最大的连续数列，并返回总和。
 *
 * 2. 算法分析
 *      本题是一道简单的算法题，有多种思路，下面我们主要针对分治算法来实现上述这个问题求解
 *      分析分治算法的实现思路：
 *             首先明确我们的目的是求出数组nums中的最大连续和，我们可以将问题转化为求出数组l到r索引子数组的
 *             的最大连续和即实现方法get(nums,l,r),则最终结果就是get(nums,0,n-1),其中n为数组的长度，如何
 *             对get(nums,l,r)进行分治呢?
 *             假设当前我们想求出数组nums的子数组l到r(包含边界)，将子数组分成两个部分nums[l,...,m],nums[m+1,...,r]
 *             其中m = [(l+r)/2],分析这个子数组的最大连续和的出现情况有哪些:
 *                 1. 以l为起始的最大连续和
 *                 2. 以r为结束的最大连续和
 *                 3. 最大连续和在中间
 *                 4. 最大连续和就是当前l到r区间
 *             简单证明可知只有这四种情况
 *             对于上述四种情况，最简单的就是第四种情况，之间求出l到r的和就可以，但是对于其他三种情况我们就需要分治来维
 *             护
 *             在分析下面的分治状态前，我们先做一些符号上的规定：
 *                 lmax：表示以l为起始的最大连续和
 *                 rmax：表示以r为结束的最大连续和
 *                 imax：表示当前区间的和
 *                 max：表示当前区间的最大连续和
 *                 left：表示划分之后的左区间
 *                 right：表示划分之后的右区间
 *                 all：表示整个当前的子区间[l,r]
 *             下面我们主要是分析出划分的区间与整个当前区间之间的的四种状态之间的关系，对于l == r时，上述四种状态是一致的
 *
 *             考虑情况1：以l为起始的最大连续和
 *                 如果最大连续和以l为起始，那么出现最大连续和的情况只有两种：1. 出现在以l为起始的划分之后的左区间
 *                 2. 以l为起始的整个做区间+右区间的lmax(因为这样才是一个连续的区间)
 *                 综上可知：all.lmax = max(left.lmax,left.imax + right.lmax)
 *
 *             考虑情况2：以r为结束的最大连续和
 *                 分析思路同上：all.rmax = max(right.rmax,right.imax+left.rmax)
 *
 *             考虑情况3：最大连续和出现在当前子数组的中间位置
 *                 如果最大连续和出现在当前数组的中间位置，此时有三种情况：1. 出现在左区间的最大连续和 2. 出现在有区间的最大
 *                 连续和 3. 出现在左区间的最大右连续和+右区间的最大左连续和
 *                 我们需要去上述三种状态下的最大值：all.max = max(max(left.max,right.max),left.rmax+right.lmax)
 *
 *         分析代码的实现：
 *             既然我们需要维护一个子区间的四种状态，所以我们可以将这个状态抽象成一个状态类名为Status,在上述的分析中我们需要
 *             当前子区间划分之后的左右区间的状态，从而确定整个区间的状态
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q001_连续数列 {

    class Status {
        int lmax;
        int rmax;
        int imax;
        int max;

        public Status(int lmax,int rmax,int imax,int max) {
            this.lmax = lmax;
            this.rmax = rmax;
            this.imax = imax;
            this.max = max;
        }
    }

    // 获取子区间[l,r]的状态类，递归实现
    public Status getSubInteverStatus(int[] nums,int l,int r) {
        if(l == r) { // 判断边界
            return new Status(nums[l],nums[l],nums[l],nums[l]);
        }
        int m = (l + r) / 2; // 此处可以使用位运算来优化效率
        Status left = getSubInteverStatus(nums,l,m);
        Status right = getSubInteverStatus(nums,m+1,r);
        return unionStatus(left,right);
    }

    // 合并左右状态，上述是分，此方法就是合
    public Status unionStatus(Status left,Status right) {
        int lmax = Math.max(left.lmax,left.imax + right.lmax);
        int rmax = Math.max(right.rmax,right.imax + left.rmax);
        int imax = left.imax + right.imax;
        int max = Math.max(Math.max(left.max,right.max),left.rmax + right.lmax);
        return new Status(lmax,rmax,imax,max);
    }

    public int maxSubArray(int[] nums) {
        return getSubInteverStatus(nums,0,nums.length - 1).max;
    }

    public static void main(String[] args) {
        System.out.println(0 | 0);
    }
}
